package com.tgy.back.tracking;

/**
 * @Author: tgy
 * @Date: 2020-10-30 11:06
 */
public class EightQueens {

    private int queens = 8;

    private byte colIsQueen;

    private short leftOblique;

    private short rightOblique;

    private int[] locals;

    private int sumQueen;

    public int queens() {

        locals = new int[queens];

        find(0);
        return sumQueen;
    }

    private void find(int row) {

        if (row == queens) {

            sumQueen++;
            return;
        }

        for (int col = 0; col < queens; col++) {

            int left =  queens - 1 + (row - col);
            int right = row + col;
            if (isQueen(col,left,right)) {

                setLocals(col,left,right,true);
                locals[row] = col;
                find(row + 1);
                setLocals(col,left,right,false);
            }
        }
    }

    /**
     *
     * @param col 对应colIsQueen的索引
     * @param left 对应leftOblique的索引
     * @param right 对应rightOblique的索引
     * @return
     */
    private boolean isQueen(int col, int left , int right) {

        if ((colIsQueen & (1<< col)) > 0){

            return false;
        }

        if ((leftOblique & (1<<left)) > 0) {

            return false;
        }

        if ((rightOblique & (1<< right)) > 0) {

            return false;
        }

        return true;
    }

    /**
     * 设置指定位置的0 1 值
     * @param col 对应colIsQueen的索引
     * @param left 对应leftOblique的索引
     * @param right 对应rightOblique的索引
     * @param type true 表示在上面对应位置设置为1, false 表示在上面对应位置设置为0
     */
    private void setLocals(int col, int left, int right, boolean type) {

        if (type) {
            // 设置对应位置为 1
            colIsQueen = (byte) (colIsQueen | (1<<col));
            leftOblique = (short) (leftOblique | (1<<left));
            rightOblique = (short)(rightOblique | (1<< right));
        }else {
            // 设置对应位置为 0
            colIsQueen = (byte) (colIsQueen & ~(1<<col));
            leftOblique = (short) (leftOblique & ~(1<<left));
            rightOblique = (short)(rightOblique & ~(1<< right));
        }
    }

}
